package leetcode.editor.cn.dsa15_stackAndGA;
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。
// 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

import java.util.Stack;

public class RemoveDuplicateLetters316_2 {
    public static void main(String[] args) {
        Solution solution = new RemoveDuplicateLetters316_2().new Solution();
        System.out.println(solution.removeDuplicateLetters("bcabc")); //abc
        System.out.println(solution.removeDuplicateLetters("cbacdcbc")); //acdb
        System.out.println(solution.removeDuplicateLetters("dcbadd")); //cbad
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 栈 + 贪心算法
         */
        public String removeDuplicateLetters(String s) {
            int len = s.length();
            // 记录字符串中出现过的字符在字符串最后一次出现的位置
            int[] lastOccurrence = new int[26];
            for (int i = 0; i < len; i++) {
                lastOccurrence[s.charAt(i) - 'a'] = i;
            }
            // 记录当前栈中已经存在的字符，方便对重复元素的判断
            boolean[] seen = new boolean[26];
            // 使用栈缓存满足条件的字符
            Stack<Character> stack = new Stack<>();
            // 从左到右扫描字符串
            for (int i = 0; i < len; i++) {
                char c = s.charAt(i);
                if (!seen[c-'a']) { // 若当前字符已经在栈中，无需处理
                    // 如果栈中有元素，且栈顶元素比当前字符大，并且栈顶字符在后续字符串还会出现：
                    // 那么我们可以用当前字符替换栈顶字符得到一个字典序更小的字符串（此处将一直与栈顶
                    // 元素相比，直到栈为空或栈顶字符比当前字符小，或栈顶字符在当前位置之后不会再出现）
                    while (!stack.isEmpty() && c < stack.peek()
                            && lastOccurrence[stack.peek() - 'a'] > i) {
                        seen[stack.pop()-'a'] = false;
                    }
                    // 其他情况都需入栈
                    stack.push(c);
                    seen[c-'a'] = true;
                }
            }
            String result = "";
            while (!stack.isEmpty()) {
                // 将栈中的字母倒序连接起来
                result = stack.pop() + result;
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}